package com.lw.leetcode.linked.b;

import com.lw.leetcode.linked.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 1171. 从链表中删去总和值为零的连续节点
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/26 15:40
 */
public class RemoveZeroSumSublists {

    public static void main(String[] args) {
        RemoveZeroSumSublists test = new RemoveZeroSumSublists();

        // [1,3,2,-3,-2,5,5,-5,1]
    }
    public ListNode removeZeroSumSublists(ListNode head) {
        int sum = 0;
        Map<Integer, ListNode> map = new HashMap<>();
        ListNode root = new ListNode(0);
        map.put(sum, root);
        root.next = head;
        while (head != null) {
            sum += head.val;
            ListNode listNode = map.get(sum);
            if (listNode == null) {
                map.put(sum, head);
            } else {
                ListNode n = listNode.next;
                int item = sum + n.val;
                while (item != sum) {
                    map.put(item, null);
                    n = n.next;
                    item = item + n.val;
                }
                listNode.next = head.next;
            }
            head = head.next;

        }
        return root.next;
    }

}
